COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00003 00003	.begin center
C00010 00004	.begin center
C00016 00005	.begin center	
C00023 ENDMK
C⊗;
.device xgp
.require "BASKER.PUB[SUB,SYS]" source_file;
.select 1
.TURN ON "{", "↑", "↓", "[", "]", "&" ;
.TURN ON "↓_"

.begin center
DISPLAY GENERATED BY A GENERALIZED CONE REPRESENTATION
.end

Eiichi  Miyamoto:  Department of  Information  Engineering,  Hokkaido
University, Sapporo, Japan. 

Thomas  O.   Binford:  Artificial  Intelligence  Laboratory, Stanford
University, Stanford, Calif, 94305. 
.begin nofill


.end
.PAGE FRAME 56 HIGH 57 WIDE;
.NEXT PAGE
.begin center
↓_ABSTRACT_↓
.end

We  describe  the  generalized  cone  representation  and   its  data
structure  for  a  class  of three-dimensional  curved  objects,  and
describe  an  algorithm for  hidden  line elimination  for displaying
objects.   In  the  generalized  cone representation,  an  object  is
represented by a  sequence of disjoint slices called cross sections,
 normal  to a space curve
called the spine.   Accordingly,  an object is  displayed with  cross
section  edges and  longitudinal  edges which  connect  corresponding
points of two adjacent cross sections. 
Modelling by generalized cones simplifies input for
curved objects. 

 The program  first suppresses hidden lines within  a
segment of a part, between two adjacent cross sections.  Lines hidden
by other segments of parts are eliminated by a brute force comparison
of one segment versus every other segment. 
.begin nofill


.end
.begin center
↓_INTRODUCTION_↓
.end

We   require   that   a   representation   give   simple   part/whole
decompositions for familiar objects,  decompositions which correspond
to  our intuitive  sense of  parts.   Like  most representations,  the
Generalized Cone representation  is a part/whole  graph of an  object
structured  into parts  by  cutting  and pasting.  The  parts may  be
structured  into  subparts  to  any  depth.    The difference  between
representations is  the choice  of primitives and  the process  which
generates  descriptions of  objects within  the representation.   The
design criteria for generalized cone primitives are: a) parts  should
be defined by continuity; b) parts should correspond to our intuitive
notion  of parts; c)  parts which we  regard as similar  should have a
simple sense  of similarity  in the  representation; d)  relationships
which we regard  as significant for shape description,  such as thin,
should be explicit.  These criteria imply that primitives should be
volumes rather than surfaces.  Most people regard a block as a single
part, rather than as six surface parts.  That is, we don't segment at
surface discontinuity.   Further, parts should be generated  by local
volumes;   our  intuitive  segmentations   require  a   rich  set  of
primitives.  We  want the local  volumes to be  disjoint for our  own
convenience  in  visualizing.    Thus, we  seek  volume  primitives
defined by  continuity.  Generalized cone primitives are defined by a
sequence of thin slices normal to some space curve  called the spine.
The  slices can  be described  by a  continuous
function (whose value is a cross section) along  the  spine.    The  representation  is  based  on the
"generalized translational invariance" formalism.  In this formalism,
normal cross sections  are mapped into other normal cross sections by
translation followed by some congruence transformation.  For example,
a cylinder is defined by any plane figure translated along a straight
line.   A  cone is  defined by  any plane  figure translated  along a
straight line,  with a  scaling function  which is  linear along  the
line. 

The representation  of  cross sections  is the  same  problem in  two
dimensions.   The  representation of cross  sections is  a part/whole
representation, with area primitives (not curve primitives) connected
by cutting and pasting.  The primitives are formalized by generalized
translational  invariance in two dimensions, expressed  in terms of a
plane curve called the spine, and straight lines normal  to the spine
(cross sections of one-dimension). 

The representation  has been used  in scene analysis  for description
and  recognition   of   curved   objects  [1,2].      The
representation  best describes  parts with  cross  sections  which  change
smoothly along some space curve.  
.begin nofill


.end

.begin center
↓_DATA STRUCTURE FOR THE REPRESENTATION_↓
.end

In  the  program,  parts are  described  as  interpolation  functions
(splines)  for samples of cross  sections normal to the  spine.  Thus
parts are  represented as  sequences of  cross sections.   The  cross
sections are described in curve  form, as interpolation functions for
curve samples.  Cross sections may be circles or combinations of line
segments and  arcs.   That  representation for  cross sections  is an
expedient;  it  is inconsistent  with  the  representation for  cross
sections  described  above.    There  are  cross  section   edges  and
longitudinal  edges  which  tie  together   corresponding  points  of
adjacent cross  sections (see figure 1).  Although arcs  or curves are now displayed
as line segments, the display of longitudinal edges connecting points
on arcs may be suppressed, because these are artifacts. 

Each sample  point along a  cross section  is specified by  Cartesian
coordinates  in  the sense  of  a  right screw  in  the  direction of
generation of  the object  (in the  order of  cross  section).   This
ordering determines the interior of the object.  Each point lies on a
cross section edge and a longitudinal edge.  Each edge may be divided
into an arbitrary number of segments by hidden line elimination. 

Each object has its own  coordinate system and a relationship  to the
coordinate system of a parent  object or of the world.  Objects which
have the  same parent  are  called siblings.    There exists  a  tree
structure among objects. 

When  objects  are   displayed,  their  local  coordinates   must  be
transformed  into  world coordinates.    Let T↓i  be  the translation
vector and let R↓i be  the rotation matrix for transformation of  the
i↑[th] child  to world coordinates.   Then we can set  up the following
relations:
.begin nofill
    T↓i = T↓[i-1]+ R↓[i-1]t↓[i-1,i], 
    R↓i = R↓[i-1]r↓[i-1,i],
.end
where T↓0  is the zero vector and  where R↓0 is the unit matrix.
Here,   t↓[i-1,i]   =   (x↓[i-1,i],y↓[i-1,i],z↓[i-1,i])↑T    is   the
translation  vector from  the i↑[th]  child  coordinate frame  to its
parent's frame, and
.begin nofill
			i↓x  j↓x  k↓x
	r↓[i-1,i] =	  i↓y  j↓y  k↓y
			i↓z  j↓z  k↓z
.end
is the rotation matrix from the coordinate  frame of the i↑[th] child
to its  parent's frame.  The rotation  can be specified by a rotation
vector for which the  direction of the  vector specifies the axis  of
rotation  and the  magnitude of  the  vector specifies  the angle  of
rotation in radians.  Given such a rotation vector w↓x, w↓y, w↓z with
direction cosines c↓x, c↓y, c↓z and magnitude W in  radians.  Let c↓w
be cos(W)  and s↓w be sin(W).   Then the relation  between a rotation
matrix and a rotation vector [3] is as follows:
.begin nofill
 	i↓x = (1-c↓w)c↓xc↓y + c↓w
	j↓x = (1-c↓w)c↓xc↓y + c↓zs↓w
	k↓x = (1-c↓w)c↓xc↓z + c↓ys↓w
	i↓y = (1-c↓w)c↓yc↓x + c↓zs↓w
	j↓y = (1-c↓w)c↓yc↓y + c↓w
	k↓y = (1-c↓w)c↓yc↓z - c↓xs↓w
	i↓z = (1-c↓w)c↓zc↓x - c↓ys↓w
	j↓z = (1-c↓w)c↓zc↓y + c↓xs↓w
	k↓z = (1-c↓w)c↓zc↓z + c↓w  .
.end

The screen is chosen as the plane z =  0, and the observer is located
at  the point (0,0,c), in  the world coordinates, where  c>0.  Then a
point  (x,y,z)   in   world  coordinates   projects  to   the   point
(cx/(c-x),cy/(c-y)) on the screen. 
.next page
.begin center	
↓_HIDDEN LINE ELIMINATION_↓
.end

Let us define a piece as the volume between  a pair of adjacent cross
sections.  First,  lines within a piece are eliminated as follows.  A
surface is  visible  if the  normal to  the  surface has  a  positive
component  along the  ray to  the observer.   An  edge is  visible if
either  surface is  visible  at the  edge.   Because of  the sense  of
ordering of cross sections, the first cross section is visible if its
edges  have a clockwise  sense on  the screen,  and the  second cross
section is visible if its edges have a counterclockwise sense on  the
screen.  If the cross section is convex, the angle between successive
edges  will be less than  pi for clockwise image,  and greaer than pi
for  counterclockwise image.    However,  if  the  cross  section  is
nonconvex, the sum  of angles between successive edges will  be 2π if
clockwise and -2π if negative. 

A  longitudinal plane is  visible if  the angle from  a cross section
edge of  the first  cross section  to  the longitudinal  edge in  the
counterclockwise sense  is less than π.     At  concavities
in cross  sections, invisible  longitudinal  planes may  hide  planes
visible by  the  above condition  (figure 2).  That  portion of  the
partially  visible  plane  which  overlaps  the  invisible  plane  is
obscured.  The results for this stage are shown in figure 3 
for the example in figure 1.

The contour edges  of a piece are  those with one visible  surface at
the  edge.    At  concavities  in  the  cross  section,  portions  of
longitudinal edges are interior to  the contour of the piece  (figure
2). 

To eliminate edges  obscured by other pieces, each  piece is compared
with  every  other  piece.    Bounding  rectangles  aligned with  the
coordinate axes of the screen are calculated, and  those pieces whose
bounding rectangles  are disjoint are  immediately ignored.   For the
rest, for  each edge  on  the contour  of a  piece,  if there  is  an
apparent intersection with  edges of the  contour of the  other piece
(within  the line intervals), it  is determined which  line is nearer
the observer at the apparent intersection. 

In cases in which the projection of an object is entirely  within the
projection of another object, there is no intersection.  To determine
this  case, the  apparent intersections  of an  extended edge  of the
contour of one piece with  the contour of the other piece  are found.
If  two intersections are  found on  different sides  of the  line, a
hypothetical line is considered between the two intersections for the
larger piece, and it is decided which edge is nearer.  This fails for
some  nonconvex  pieces.    If  the  projections  of  the  pieces  are
disjoint, the two intersections fall on the same side of the line. 

After the decision of  which piece is  closer, every visible line  of
the further  piece is  checked to remove  the hidden  portion between
apparent  crossing points with  the contour of  the occluding piece.  
Figures 4 and 5 demonstrate complex objects after execution  of hidden line
elimination. 
.begin nofill


.end

.begin center
↓_CONCLUSION_↓
.end

The representation of an  object by disjoint slices is convenient for
use in  vision and  planning for  manipulation.   In this  case,  the
primary advantages are ease of input, display  of curved objects with
no artifact edges,  and compact data structure.  The program is being
extended  to   adequately  deal   with  hollow   objects  and   other
nonconvexities. 

References:

1) R.K.Nevatia,"Structured Descriptions of Complex Curved Objects for
Recognition and Visual Memory", Stanford Artificial Intelligence 
Laboratory Memo AIM-250, October 1974.

2) G.J.Agin,"Representation and Description of Curved Objects", Stanford
Artificial Intelligence Laboratory Memo AIM-173, October 1972.

3) Bruce  G. Baumgart;  "Geometric Modeling  for Computer
Vision";  Stanford Artificial Intelligence  Laboratory, Memo AIM-249,
Stanford University, October 1974.